We present two universal hinge patterns that enable a strip of material tofold into any connected surface made up of unit squares on the 3D cubegrid--for example, the surface of any polycube. The folding is efficient: fortarget surfaces topologically equivalent to a sphere, the strip needs to haveonly twice the target surface area, and the folding stacks at most two layersof material anywhere. These geometric results offer a new way to buildprogrammable matter that is substantially more efficient than what is possiblewith a square $N \times N$ sheet of material, which can fold into all polycubesonly of surface area $O(N)$ and may stack $\Theta(N^2)$ layers at one point. Wealso show how our strip foldings can be executed by a rigid motion withoutcollisions, which is not possible in general with 2D sheet folding. To achieve these results, we develop new approximation algorithms for millingthe surface of a grid polyhedron, which simultaneously give a 2-approximationin tour length and an 8/3-approximation in the number of turns. Both length andturns consume area when folding a strip, so we build on past approximationalgorithms for these two objectives from 2D milling.
展开▼
